class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None


# 访问节点值
# class Solution(object):
#     def inorderSuccessor(self, node):
#         """
#         :type node: Node
#         :rtype: Node
#         """
#         if node.right:
#             node = node.right
#             while node.left:
#                 node = node.left
#             return node
#         else:
#             parent = node.parent
#             if not parent:
#                 return None
#             else:
#                 if parent.val > node.val:
#                     return parent
#                 else:
#                     while parent and parent.val < node.val:
#                         parent = parent.parent
#                     return parent


class Solution(object):
    def inorderSuccessor(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if node.right:
            node = node.right
            while node.left:
                node = node.left
            return node
        else:
            parent = node.parent
            if not parent:
                return None
            else:
                if parent.left == node:
                    return parent
                else:
                    while parent and parent.right == node:
                        node = parent
                        parent = node.parent
                    return parent